package org.jeecg.modules.utils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {
    public static List<List<Integer>> findCombinations(int[] nums, int target) {
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> currentCombination = new ArrayList<>();

        backtrack(nums, target, 0, 0, currentCombination, combinations);

        return combinations;
    }

    private static void backtrack(int[] nums, int target, int start, int currentSum,
                                  List<Integer> currentCombination, List<List<Integer>> combinations) {
        if (currentSum == target) {
            combinations.add(new ArrayList<>(currentCombination));
            return; // 终止条件，避免继续递归查找
        }
        if (currentSum >= target) {
            return;
        }

        for (int i = start; i < nums.length; i++) {
            int num = nums[i];
            currentCombination.add(num);
            backtrack(nums, target, i+1, currentSum + num, currentCombination, combinations);
            currentCombination.remove(currentCombination.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6};
        int target = 7;

        List<List<Integer>> combinations = findCombinations(nums, target);
        System.out.println("组合列表：");
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }
    }
}
